1423. Maximum Points You Can Obtain from Cards
Medium

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

 

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

 

Constraints:

  • 1 <= cardPoints.length <= 105
  • 1 <= cardPoints[i] <= 104
  • 1 <= k <= cardPoints.length
Accepted
83.9K
Submissions
172.9K
Seen this question in a real interview before?
Companies
Show Hint 1
Let the sum of all points be total_pts. You need to remove a sub-array from cardPoints with length n - k.
Show Hint 2
Keep a window of size n - k over the array. The answer is max(answer, total_pts - sumOfCurrentWindow)

Average Rating: 4.97 (34 votes)

Premium

Solution


Overview

The brute force solution is to find all valid combinations of cards and then select the combination that gives us the maximum sum. To accomplish this, we can use a recursive approach. At each point, we choose a card either from the beginning or from the end of the array. Our base condition is when k cards are selected or when no cards are left to be selected. This solution results in TLE because it checks an exponential number of combinations (many of the same combinations would be checked more than once). We can optimize this solution by using a dynamic programming approach.

A key observation in this problem is that we need to select k cards from the beginning or end of the array. Thus no matter how many cards we choose from the beginning, in the end, we need to select two subarrays: one from the beginning, and one from the end, and their total lengths must be k (the only exception is when k = cardPoints.length, in that case, we'll select all cards). Thus after selecting the two arrays we will be left with a single subarray of length cardPoints.length - k. There are three ways we can select the cards:

  1. Select all cards from the beginning.
  2. Select all cards from the end.
  3. Select some cards from the beginning and the rest from the end.

In all the above three cases we will be left with a subarray (in the end, in the beginning, or somewhere in the middle) after our selection. This can be better understood in the following illustration where we are selecting 3 cards from an array of 8 cards.

fig

Figure 1. An example demonstrating some of the positions of the subarrays possible from selecting k = 3 cards from the array.

In addition to the dynamic programming approach, we can also take a sliding window approach. A sliding window is a standard programming pattern used in many problems, including those related to finding the sum or the product of a subarray. In case you are not familiar with sliding windows, you can go through this article written by one of our LeetCode users: Sliding Window Problems for Beginners. In this article, we'll start by looking at the dynamic programming approach and discuss how to optimize its space complexity. After that, we will finish with the sliding window approach.



Approach 1: Dynamic Programming

Intuition

As we determined above, the k cards that we choose will form two contiguous subarrays: one at the start, and one at the end of the input array. If we choose i cards from the start (where i <= k) then we must choose k - i cards from the end. There are k different lengths the first array could be.

Since these k arrays are overlapping, we can calculate the prefix sum for each of the first k values, and then for each of the last k values (working from the end of the array, and going inwards). We will store these values in two arrays of size k.

We can then use these to efficiently check each possible way of selecting i cards from the start and k - i cards from the end.

Current
1 / 6

Algorithm

  1. Initialize two arrays of size k + 1, namely frontSetOfCards and rearSetOfCards to store the score (prefix sums) obtained by selecting the first i cards and the last i cards in the array.

  2. We calculate the prefix sum (sum of 0 <= i <= k cards) for the first k cards frontSetOfCards[i + 1] = frontSetOfCards[i] + cardPoints[i] and the last k cards rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i].

  3. Initialize maxScore to 0.

  4. Iterate from i = 0 -> k. At each iteration, we determine the possible score by selecting i cards from the beginning of the array and k - i cards from the end (currentScore). If this score is greater than the maxScore then we update it.

Implementation

Complexity Analysis

Let kk be the number of cards we need to select.

  • Time complexity: O(k)O(k). Here we are using two for loops of length k to calculate the maximum possible score. This gives us O(2k)O(2 \cdot k), which in Big O notation is equal to O(k)O(k).

  • Space complexity: O(k)O(k). Here we are using two arrays to store the total score obtained by selecting i(0<=i<k)i(0 <= i < k) cards from the beginning and ii cards from the end. This gives us O(2k)O(2 \cdot k), which is equal to O(k)O(k).



Approach 2: Dynamic Programming - Space Optimized

Intuition

In approach 1 we used two extra storage spaces (two arrays of size k) to store the total score that can be obtained by taking i cards from the respective end of the array.

Instead of pre-computing the arrays, we can calculate the total score while iterating over the array and store the total score in two variables (in place of the two arrays).

Algorithm

  1. Initialize two variables, namely frontScore and rearScore to store the score obtained by selecting the first i cards and the last k - i cards in the array.

  2. frontScore is initialized to the sum of the first k cards in the array, and rearScore is initialized to 0.

  3. Initialize maxScore to frontScore.

  4. Iterate backwards from i = k - 1 -> 0. At each iteration, we calculate the score by selecting i cards from the beginning of the array and k - i cards from the end (currentScore). If this score is greater than maxScore, we update it.

Implementation

Complexity Analysis

Let kk be the number of cards we need to select.

  • Time complexity: O(k)O(k). We are using two for loops of length k for calculation purposes. This gives us O(2k)O(2 \cdot k), which in Big O notation is equal to O(k)O(k).

  • Space complexity: O(1)O(1). No extra space is used since all the calculations are done impromptu.



Approach 3: Sliding Window

Intuition

In this problem, we must draw exactly k cards from the array in such a way that the score (sum of the cards) is maximized. After drawing k cards from the array cardPoints.length - k cards will remain in the array.

Another way that we could view the problem is that our objective is to choose cards from the beginning or end of the array in such a way that the sum of the remaining cards is minimized.

We can use a sliding window to find the subarray of size cardPoints.length - k that has the minimal sum. Subtracting this value from the total sum of all the cards will give us our answer. This is because no matter where the minimum subarray is located (in the beginning, the middle, or the end) the remaining cards must be selected under the given rule: in one step, you can take one card from the beginning or the end of the array.

Algorithm

  1. Find the sum of all cards in the array and store it in a variable totalScore.

  2. If k is equal to cardPoints.length, then return totalScore.

  3. Initialize requiredSubarrayLength to cardPoints.length - k.

  4. Initialize two variables: presentSubarrayScore and startingIndex to 0. This startingIndex marks the starting point of the subarray presently under consideration. Thus it keeps track of the length of the present subarray.

  5. Initialize a variable minSubarrayScore to totalScore. When the algorithm completes, this variable will hold the smallest possible subarray score in the input array.

  6. Iterate over the array.

    • At each iteration add the current card to presentSubarrayScore.
  7. If the size of the subarray under consideration presentSubarrayLength is equal to the requiredSubarrayLength:

    • Compare the score of the subarray presentSubarrayScore with the minSubarrayScore and modify the minSubarrayScore so that it stores the minimum possible subarray sum.
    • Subtract the current card from the presentSubarrayScore.
    • Increment the startingIndex.
  8. Subtract the minSubarrayScore from the totalScore to get the maximum total score that can be obtained by picking k cards from the beginning or the end of the array. Return this value.

Implementation

Complexity Analysis

Let nn be the number of cards we need to select.

  • Time complexity: O(n)O(n). In the problem, we are iterating over the array of cards twice. So the time complexity will be O(2n)O(2 \cdot n) = O(n)O(n).

  • Space complexity: O(1)O(1) since no extra space is required.



Report Article Issue

Comments: 10
olajohn-ajiboye's avatar
Read More

Finally, a solution that uses sensible variable names. I don't get why this is rampant. I was so used to it from Leetcode that I got a critical review in one interview because of this.

It just makes it easier to understand code without much explanation that useless shorth variable names look so ugly.

19
Reply
Share
Report
Satyr's avatar
Read More

One of the better-written solutions on LC. Nice!

6
Reply
Share
Report
jca88's avatar
Read More

I know the backtracking approach gets TLE, but for this post (and similar posts) would it be possible to have it as an approach and show the code? It's just I'm starting see that every problem can be solved recursively and it would be good to how its done :)

3
Show 2 replies
Reply
Share
Report
florin5's avatar
Read More

This problem benefits from an implementation in Python, a language more expressive when dealing with stream processing, for example, the sliding window approach is quite terse :

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        s = sum(cardPoints)
        window = sum(cardPoints[:(len(cardPoints)-k)])
        r =s -window
        for i in range(k):
            window+=cardPoints[i+len(cardPoints)-k] -cardPoints[i]
            r= max(r,s -window)
        return r

1
Reply
Share
Report
yelun's avatar
Read More

Java solution O(k) with explanation

 public int maxScore(int[] nums, int k) {        
        int sum = 0;
        int left = 0;
        int right = k - 1;
        
        // init the base case which starts from 0 ... k - 1
        for (int i = 0; i < k; i++){
            sum += nums[i];            
        }
        
        if (k == nums.length){ // early return as there is only one solution
            return sum;
        }
        
        // recognize that this is fixed length window that wraps around end of array        
        // e.x. [a, b, c, d, e, f, g] and k = 3
        // can take at most between e, f, g ("negative array") to a, b, c, (positive array)
        int newSum = sum; // save the initial state sum (from 0 .. k-1) for comparison
        for (int i = 0; i < k; i++){
            // do a rotation
            newSum -= nums[right]; // remove element from end of positive array which is always >= 0
            right--;
            
            // add element from the beginning, which is always "negative"                       
            left --;
            newSum += nums[nums.length + left];            
            
            sum = Math.max(newSum, sum);
        }
        
        return sum;
    }

0
Reply
Share
Report
onurerkinsucu's avatar
Read More

In my solution if I use the for loop as the following way it works correctly: int z = cardPoints.size() - k;
for(int i = cardPoints.size() - 1; i >= z; i--){

However, in the following way, although the testcase work correctly, submission gives an error:
for(int i = cardPoints.size() - 1; i >= cardPoints.size() - k; i--){
error occurs because "i" may become negative which should not be happen.
Why this is happening can someone explain?

0
Show 2 replies
Reply
Share
Report
jinhuang1102's avatar
Read More

The Sliding Window is good to understand! Here is my Python version code:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        totalScore = sum(cardPoints)
        if k == len(cardPoints):
            return totalScore
        
        reqLen = len(cardPoints) - k
        idx = 0
        curScore = 0
        minScore = totalScore
        
        for i in range(len(cardPoints)):
            curScore += cardPoints[i]
            curLen = i - idx + 1
            
            if curLen == reqLen:
                minScore = min(minScore, curScore)
                
                curScore -= cardPoints[idx]
                idx += 1
                
        return totalScore - minScore

0
Reply
Share
Report
Netaji51's avatar
Read More

Java solution O(k)

public int maxScore(int[] cardPoints, int k) {

    int n = cardPoints.length;
    
    int sum=0, answer=0;
    
    for(int i=0;i<k;i++){
        sum += cardPoints[i];
    }
    
    answer = sum;
    
    for(int i=k-1,j=n-1;i>=0 && j>=n-k;i--,j--){
        sum -= cardPoints[i];
        sum += cardPoints[j];
        
        answer = Math.max(answer, sum);
    }
    
    return answer;
}

0
Reply
Share
Report
sameeraswal's avatar
Read More

We can calculate sum of the minimum widnow and array elements in one go:-

var maxScore = function(cardPoints, k) {
    /*In every possible ans there will be a continues window of the size cardPoints.length-k for which we will not collect the points. We need to check that window of the size cardPoints.length-k with the having minimum sum. 
    Then we can remove this minimu sum of the windown from total array sum. This will be our answer.
    */
    let windowSize=cardPoints.length-k,arrSum=0,minWindowSum=Number.MAX_SAFE_INTEGER,windowSum=0;
    for(let i=0;i<cardPoints.length;i++){
        arrSum+=cardPoints[i];
        if(i<=windowSize-1){
            windowSum+=cardPoints[i];
        }else{
            windowSum+=cardPoints[i];
            windowSum-=cardPoints[i-windowSize];
        }
        if(i>=windowSize-1){
            minWindowSum = Math.min(minWindowSum,windowSum);
        }
    }
    return arrSum-minWindowSum;
}

0
Reply
Share
Report
mehakwaliaC's avatar
Read More

Is it just me or choosing i and j without getting boundary overflow errors a big deal. It gives me a headache!

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/25/2021 13:09Accepted56 ms42.4 MBcpp
05/25/2021 12:58Time Limit ExceededN/AN/Acpp
05/11/2021 18:57Accepted52 ms45.8 MBcpp
05/11/2021 18:55Wrong AnswerN/AN/Acpp
05/02/2020 16:57Wrong AnswerN/AN/Acpp
05/02/2020 16:55Wrong AnswerN/AN/Acpp
05/02/2020 16:49Wrong AnswerN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium